package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;

/**
 * 二叉树训练
 * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 *
 * 路径和 是路径中各节点值的总和。
 *
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution124 {
    private int MAX_VAL = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root ==null){
            return 0;
        }
        dfs(root);
        return MAX_VAL;

    }

    /**
     * 计算分为三种情况 一种a,b,c a +b+c a+b+a的父节点 a+c+a的父节点
     * 如果节点的值为负数直接舍弃 不如不加
     * @param treeNode
     * @return
     */
    private int dfs(TreeNode treeNode){
        if (treeNode ==null) {
            return 0;
        }
        // 计算 左边的
        int left = Math.max(0,dfs(treeNode.left));
        int right = Math.max(0,dfs(treeNode.right));
        MAX_VAL = Math.max(MAX_VAL,treeNode.val+left+right);
        // 返回经过root的单边最大分支给当前root的父节点计算使用
        return treeNode.val + Math.max(left, right);

    }
}
